1. Field of the Invention
The present invention relates to a method and apparatus for extracting a connected element which has continuity and connectedness in a binary image, particularly to same requiring small amount of storage capacity.
In recent years, a labeling technique for extracting the connected element is becoming more and more important as a means to analyze an image and cut out characters and figures, etc. from the image. For instance, the labeling technique is used for an optical character recognition device (OCR) as a pre-processing means to cut out individual character elements from individual handwritten characters. It is also used in a wide variety of applications for image processing including inspection and monitoring of an image.
2. Description of the Related Art
FIG. 1 illustrates a conventional method for extracting and labeling a connected element.
In a conventional method, a label processor calculates from input binary image data, a connected element having image-representing pixels connected in one in a binary image (three connected elements are shown in FIG. 1) and provides a label to the connected element. The label processor stores the labeled connected elements (labeled 1, 2 and 3 in FIG. 1) in a label image storage as a label image data for later use in image processing (e.g., image analysis and document image processing) by an image processing unit (not shown).
The label processing method used here is known by "Raster Scan-type Label Processing Method" (Japanese Patent Application Provisional Number (TOKUGANHEI) 03-206574) and "Label Processing Method" (Japanese Patent Application Provisional Number (TOKUGANHEI) 05-237552), for example.
However, the conventional method labels connected elements of the input binary image and stores the data as label image data, storage capacity required for storing the label image data increases in proportion to the number of connected elements. Since labeling 255 connected elements, for example, requires 8 bits per pixel and the pixel is represented using 1 bit in the input binary image, data amount required for storing label image data is 8 times the number of pixels included in an entire picture. That is, assuming that the number of pixels in the picture is n, the storage capacity required amounts to 8n.
In usual image processing, the number of labels included in a picture is much more than 255, e.g., 64K (K=1024) or 4 G (G=1024.sup.3), requiring 16 bits or 32 bits per pixel, respectively. Therefore, the data amount required is 16 or 32 times the number of pixels included in the picture, respectively. Accordingly, it is a problem with the conventional method that an enormous amount of storage capacity is required when the label processing is performed on the input binary image data. Especially when a general-purpose processor is used for label processing, it is a problem that processing speed is remarkably reduced due to lack of storage capacity.